/*
题目: 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
https://leetcode.cn/problems/chou-shu-lcof/
 */
public class Offer49 {
    public int nthUglyNumber(int n) {
        Set<Long> set = new HashSet<> ();
        PriorityQueue<Long> heap = new PriorityQueue<> ();
        int[] factors = new int[] {2, 3, 5};
        heap.offer(1L);
        long x = 1;

        for (int i = 1; i < n; i++) {
            x = heap.poll();
            for (int j = 0; j < 3; j++) {
                long tmp = x * factors[j];
                if (set.add(tmp)) {  //如果添加成功会返回true
                    heap.offer(tmp);
                }
            }
        }
        long ret = heap.peek();
        return (int)ret;
        //return (int)heap.peek(); × , Long没法转成int
    }
}
